/*
你将会获得一系列视频片段，这些片段来自于一项持续时长为 T 秒的体育赛事。这些片段可能有所重叠，也可能长度不一。
视频片段 clips[i] 都用区间进行表示：开始于 clips[i][0] 并于 clips[i][1] 结束。
我们甚至可以对这些片段自由地再剪辑，例如片段 [0, 7] 可以剪切成 [0, 1] + [1, 3] + [3, 7] 三部分。

我们需要将这些片段进行再剪辑，并将剪辑后的内容拼接成覆盖整个运动过程的片段（[0, T]）。
返回所需片段的最小数目，如果无法完成该任务，则返回 -1 。

注意，你可能录制超过比赛结束时间的视频。

方法：贪心
	首先预处理输入序列，因为若要最小化区间数，那么以i为起点时的区间必定是最右可达最远的
	则设置一个数组记录以i为起点，最远可达的位置
	
	然后设置当前确定的最远可达位置，和一个记录达到最远时未来可能达到的最远位置（便于在达到当前最远时进行更新）
	当当前位置等于未来最远位置时，表示不可能继续前进了，返回-1
	当当前位置等于确定可达位置时，更新目前的未来最远可达距离并递增区间数
	（对于更新中的最远距离，包含了以i为起点的最远位置，若位置i值不小于那个位置，则必定无法前进）
 */

class Solution {
    public int videoStitching(int[][] clips, int T) {
        // maxn[i]表示以i为起点最远可达
        int[] maxn = new int[T];
        for (int[] t : clips) {
            if (t[0] < T) {
                maxn[t[0]] = Math.max(maxn[t[0]], t[1]);
            }
        }

        int res = 0;
        int pre = 0;  // 确定的最远距离
        int last = 0;  // 更新中的最远距离
        for (int i = 0; i < T; i ++) {
            last = Math.max(last, maxn[i]);  // 更新
            if (i == pre) {  // 到达确定可达时更新最远距离和区间数
                pre = last;
                res ++;
            }
            if (i == last) {  // 当前点无法继续则退出
                return -1;
            }
        }

        return res;
    }
}